注意题目中的这句话 : 使得同组内的两座塔的曼哈顿距离的最大值最小 , 很容易想到二分。
考虑二分一个长度，显然，当两个点的曼哈顿距离大于时，它们不能属于同一个集合。
我们将这样的点对连一条边，原问题等价与判断新图是否为一个二分图。
这个很好做到，我们找一个未被遍历的点，并向他的子节点扩散。
如果的子节点未染色，就染成与点相反的颜色。
不然，如果点的颜色与点的颜色相同，说明原图不是二分图。
重复以上操作，直到遍历完每一条边。
然后，我们发现，方案数为2的联通块数量次方。因为每个联通快的x部和y部可以交换，就有两种分法。联通块数量可以在遍历图时顺便求出。
其实此题并不难，远远不到黑题水准。
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define Mod 1000000007
const int MAXN = 5000;
int n , m , u , v , num , Ans;
struct node1{
int x , y;
}Point[ MAXN + 5 ];
int Fabs( int x ) {
return x < 0 ? -x : x;
}
int Dis( int p1 , int p2 ) {
return Fabs( Point[ p1 ].x - Point[ p2 ].x ) + Fabs( Point[ p1 ].y - Point[ p2 ].y );
}
int Quick_pow( int x , int po ) {
int Ans = 1;
while( po ) {
if( po % 2 )
Ans = 1ll * Ans * x % Mod;
x = 1ll * x * x % Mod;
po /= 2;
}
return Ans;
}
int Color[ MAXN + 5 ];
bool dfs( int u , int len ) {
for( int v = 1 ; v <= n ; v ++ ) {
if( u == v || Dis( u , v ) <= len ) continue;
if( Color[ v ] == -1 ) {
Color[ v ] = !Color[ u ];
if( !dfs( v , len ) ) return 0;
}
else if( Color[ v ] == Color[ u ] )
return 0;
}
return 1;
}
bool check( int len ) {
int cnt = 0;
memset( Color , -1 , sizeof( Color ) );
for( int i = 1 ; i <= n ; i ++ )
if( Color[ i ] == -1 ) {
cnt ++;
if( !dfs( i , len ) ) return 0;
}
Ans = len , num = cnt;
return 1;
}
int solve( ) {
int l = 0 , r = 10000 , Mid;
while( l <= r ) {
Mid = ( l + r ) / 2;
if( check( Mid ) )
r = Mid - 1;
else
l = Mid + 1;
}
return Ans;
}
int main( ) {
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d %d", &Point[ i ].x , &Point[ i ].y );
printf("%d\n", solve( ) );
printf("%d\n", Quick_pow( 2 , num ) );
return 0;
}
